package com.wfm.leetcode.editor.cn;
public class PTwo13打家劫舍II{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        int length = nums.length;
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }
    public int robRange(int[] nums,int l,int r) {
        if(nums.length==1) return nums[0];
        if(nums.length==2) return Math.max(nums[0],nums[1]);
        int n = nums.length;
        int[] dp = new int[n];
        dp[l]=nums[l];
        dp[l+1]=Math.max(nums[l],nums[l+1]);
        for(int i = l+2;i<=r;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[r];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PTwo13打家劫舍II().new Solution();
    }
}